/*
题目：从先序遍历还原二叉树
我们从二叉树的根节点 root 开始进行深度优先搜索。

在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。

如果节点只有一个子节点，那么保证该子节点为左子节点。

给出遍历输出 S，还原树并返回其根节点 root。
https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal/
 */
public class RecoverFromPreorder {
    int i = 0;

    public TreeNode recoverFromPreorder(String traversal) {
        Stack<TreeNode> stack = new Stack<> ();
        int curDepth = 0;//记录当前深度

        //先处理根节点
        TreeNode head = new TreeNode();
        head.val = getCurVal(traversal);
        stack.push(head);

        while (i < traversal.length()) {
            int depth = 0;
            //记录下一个节点的深度
            while (traversal.charAt(i) == '-') {
                depth++;
                i++;
            }

            TreeNode root = new TreeNode();
            root.val = getCurVal(traversal);

            if (curDepth >= depth) {
                while (!stack.isEmpty() && curDepth >= depth) {
                    stack.pop();
                    curDepth--;
                }
                stack.peek().right = root;
                stack.push(root);
            } else {
                stack.peek().left = root;
                stack.push(root);
            }

            curDepth = depth; //更新当前的深度
        }

        return head;
    }

    private int getCurVal(String traversal) {
        int ret = 0;
        while (i < traversal.length() && traversal.charAt(i) != '-') {
            ret = ret * 10 + (traversal.charAt(i) - '0'); //节点值更新
            i++;
        }
        return ret;
    }
}
